package day42_695;

import java.sql.Savepoint;
import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName Solution
 * @Description TODO
 * @Author clockTown
 * @Date 2021/6/20 19:30
 * @Version 1.0
 */
public class Solution {
    private int[][] grid;
    private int maxRow;
    private int maxColumn;


    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        this.maxRow = grid.length;
        this.maxColumn = grid[0].length;

        boolean[][] visited = new boolean[maxRow][maxColumn];
        int maxArea = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[row].length; column++) {
                int dfsRes = dfs(visited, row, column);
                maxArea = Math.max(maxArea, dfsRes);
            }
        }
        return maxArea;
    }

    private int dfs(boolean[][] visited, int row, int column) {
        if (row < 0 || column < 0 || row >= maxRow || column >= maxColumn || visited[row][column] || grid[row][column] == 0) {
            return 0;
        }
        int count = 1;
        visited[row][column] = true;
        int up = dfs(visited, row - 1, column);
        int down = dfs(visited, row + 1, column);
        int left = dfs(visited, row, column - 1);
        int right = dfs(visited, row, column + 1);
        return count + left + right + up + down;
    }

    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0},
        };
        System.out.println(new Solution().maxAreaOfIsland(grid));
    }
}
